package algorithm.middle;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

/**
 * 实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。
 * <p>
 * 当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
 * <p>
 * 日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end 。
 * <p>
 * 实现 MyCalendar 类：
 * <p>
 * MyCalendar() 初始化日历对象。
 * boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/my-calendar-i
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MyCalendar729 {
    //模拟
    List<int[]> list;


    public MyCalendar729() {
        list = new ArrayList<>();
        treeSet = new TreeSet<>(Comparator.comparingInt(o -> o[0]));
    }

    public boolean book(int start, int end) {
        //后闭区间
        end--;
        for (int[] arr : list) {
            int l = arr[0], r = arr[1];
            if (start > r || end < l) {
                //当前插入区间与遍历到的区间不冲突，继续比对下一个
                continue;
            } else {
                return false;
            }
        }
        list.add(new int[]{start, end});
        return true;
    }

    //二分查找
    TreeSet<int[]> treeSet;

    /**
     * 找到比end大的区间[a1,a2]
     * 找到[a1,a2]前面一个的区间[b1,b2]
     * 插入要求：b2<=start<end<=a1
     */
    public boolean book2(int start, int end) {
        if (treeSet.isEmpty()) {
            treeSet.add(new int[]{start, end});
            return true;
        }
        int[] tmp = {end, 0};
        //arr后一个
        int[] arr = treeSet.ceiling(tmp);
        //arr为set第一个，则可以直接插入tmp区间
        //此外。arr若为null，说明tmp左边必有一个区间，不存在null情况
        if (arr == treeSet.first() || treeSet.lower(tmp)[1] <= start) {
            treeSet.add(new int[]{start, end});
            return true;
        }
        return false;
    }

}
